Trong suốt cả sự nghiệp, Redondo chỉ khoác áo đội tuyển Argentina 29 lần và ghi được 1 bàn thắng.

Redondo gây ra một tin đồn khi anh từ chối khoác áo đội tuyển quốc gia tại World Cup 1990 vì lý do bận học ở trường đại học. Tại World Cup 1994 tổ chức tại Mỹ, Redondo đã tỏa sáng bên cạnh huyền thoại Diego Maradona. Sau khi Maradona bị cấm thi đấu vì sử dụng dopping, Argentina của Redondo đã dừng bước trước Romania do Geogre Hagi dẫn dắt tại vòng 16 đội với tỷ số 2-3. Đây được xem là một trong những trận đấu hay nhất qua các kỳ World Cup nói chung và sự nghệp của Redondo nói riêng.

Năm 1998, huấn luyện viên đội tuyển Argentina Daniel Passarella gạch tên Redondo khỏi danh sách tham dự World Cup vì một trong những lý do ngớ ngẩn nhất của lịch sử bóng đá thế giới: ông không đồng ý Redondo để tóc dài! Redondo nói "chẳng có lý do gì lại phải tuân theo đề nghị chẳng liên quan gì đến bóng đá như thế"[1]. Ngoài Redondo, Ariel Ortega, Gabriel Batistuta và Claudio Caniggia cũng bị gạch tên vì lý do tương tự (Ortega và Batistuta cuối cùng đã phải cắt tóc để được đi đá World Cup). Tuy nhiên, đó vẫn là một kỳ World Cup thất bại toàn diện của đội tuyển Argentina khi họ bị loại ở tứ kết bởi Hà Lan, một giải đấu mà họ được ấn tượng là "bạo lực (trong trận đấu với tuyển Anh), rườm rà, thiếu tính sáng tạo và không có bản sắc."

Sau World Cup 1998, Redondo đã từ chối khoác áo đội tuyển quốc gia[2]. Tới năm 1999, huấn luyện viên Marcelo Bielsa gọi Redondo trở lại trong trận giao hữu với Brazil. Anh được chọn là cầu thủ xuất sắc nhất trận đấu đó. Năm 2001, Redondo chính thức tuyên bố giã từ sự nghiệp quốc tế.